#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# ======================================================
# @File:      : test79
# @Author     : forward_huan
# @Date       : 2024/11/20 23:02
# @Desc       :
# ======================================================
from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        max_row, max_col, result = len(board), len(board[0]), [False]
        visited = [[0] * max_col for _ in range(max_row)]
        for row in range(max_row):
            for col in range(max_col):
                if self.checked(row, col, max_row, max_col, 0, board, word, visited):
                    return True
        return False

    @staticmethod
    def is_valid(row, col, max_row, max_col):
        return 0 <= row < max_row and 0 <= col < max_col

    def checked(self, row, col, max_row, max_col, cur_cnt, board, word, visited):
        if cur_cnt == len(word):
            return True
        if not self.is_valid(row, col, max_row, max_col) or visited[row][col] == 1 or board[row][col] != word[cur_cnt]:
            return False
        visited[row][col] = 1
        if self.checked(row, col + 1, max_row, max_col, cur_cnt + 1, board, word, visited):
            return True
        if self.checked(row, col - 1, max_row, max_col, cur_cnt + 1, board, word, visited):
            return True
        if self.checked(row + 1, col, max_row, max_col, cur_cnt + 1, board, word, visited):
            return True
        if self.checked(row - 1, col, max_row, max_col, cur_cnt + 1, board, word, visited):
            return True
        visited[row][col] = 0
        return False

print(Solution().exist(board=[["a", "b"]], word="ba"))
print(Solution().exist(board=[["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word="ABCCED"))
print(Solution().exist(board=[["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word="SEE"))
print(Solution().exist(board=[["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word="ABCB"))
